package com.hardy.leecode;

/**
 * Author: Hardy
 * Date:   2020/12/11
 * Description:
 **/
public class QueOffer45 {

    public static void main(String[] args) {
        int[] a = {10, 2};
        System.out.println(new Solution().minNumber(a));
    }

    static class Solution {

        public String minNumber(int[] nums) {
            String[] strs = new String[nums.length];
            for (int i = 0; i < nums.length; i++)
                strs[i] = String.valueOf(nums[i]);

            fast(0, nums.length - 1, strs);

            StringBuilder res = new StringBuilder();
            for (String s : strs)
                res.append(s);
            return res.toString();
        }

        public void fast(int i, int j, String[] a) {
            if (i >= j) return;

            int l = i;
            int r = j;
            String s = a[i];
            while (i < j) {
                while ((s + a[j]).compareTo(a[j] + s) <= 0 && i < j) j--;
                while ((s + a[i]).compareTo(a[i] + s) >= 0 && i < j) i++;

                String t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
            a[l] = a[i];
            a[i] = s;

            fast(l, i - 1, a);
            fast(i + 1, r, a);
        }

        void fastSort(String[] strs, int l, int r) {
            if (l >= r) return;
            int i = l, j = r;
            String tmp = strs[i];
            while (i < j) {
                while ((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--;
                while ((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++;
                tmp = strs[i];
                strs[i] = strs[j];
                strs[j] = tmp;
            }
            strs[i] = strs[l];
            strs[l] = tmp;
            fastSort(strs, l, i - 1);
            fastSort(strs, i + 1, r);
        }

    }
}
